package leetcode_900;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 *@author 周杨
 *ImageOverlap_835 给定二维数组A和二维数组B 问A能通过上下左右移动 最多能和B中有多少1的重叠
 *describe:其实就是判断曼哈顿距离 用map映射 AC 7%
 *2018年10月31日 上午11:40:35
 */
public class ImageOverlap_835 {
	public static void main(String[] args) {
		Map<int[],Integer> map=new HashMap<int[],Integer>();//用引用类型做key并不能每次能找到value
		int [] diff=new int[] {1,1};
		map.put(diff, 1);
		System.out.println(map.getOrDefault(new int[] {1, 1},0));
	}
	class Point{
		int x;
		int y;
		public Point(int x,int y) {
			this.x=x;
			this.y=y;
		}
	}
	public int largestOverlap(int[][] A, int[][] B) {
        List<Point> listA=new ArrayList<Point>();
        List<Point> listB=new ArrayList<Point>();
        for(int i=0;i<A.length;++i) {
        	for(int j=0;j<A[0].length;++j) {
        		if(A[i][j]==1)
        			listA.add(new Point(i,j));
        	}
        }
        for(int i=0;i<B.length;++i) {
        	for(int j=0;j<B[0].length;++j) {
        		if(B[i][j]==1)
        			listB.add(new Point(i,j));
        	}
        }
        Map<Integer,Map<Integer,Integer>> map=new HashMap<Integer,Map<Integer,Integer>>();
        int res=0;
        for(Point p1:listA) {
        	for(Point p2:listB) {
        		int diffx=p1.x-p2.x;
        		int diffy=p1.y-p2.y;
        		Map<Integer,Integer> now=map.get(diffx);
        		if(now==null) {
        			now=new HashMap<Integer,Integer>();
        			now.put(diffy, 1);
        			res=Math.max(1, res);
        		}
        		else {
        			int count=now.getOrDefault(diffy,0)+1;
        			now.put(diffy, count);
        			res=Math.max(res, count);
        		}
                map.put(diffx,now);
        	}
        }
        return res;
    }
}
